1. Field of Invention
The present invention relates generally to determining relationships between objects in object-based systems. More particularly, the present invention relates to efficiently performing subtype checks on objects in object-based systems.
2. Description of the Relevant Art
Many object-based computing systems are structured such that objects are members of specific classes and sub-classes which define the functionality that is available to the objects. During program execution, a virtual machine typically checks relationships between objects in order to facilitate the execution of the program. By way of example, a virtual machine may check sub-class, or subtype, relationships between objects. In some programming languages, e.g., the Java(trademark) programming language developed by Sun Microsystems, Inc. of Palo Alto, California, constructs within the programming languages involve sub-class checks. Such sub-class checks generally involve determinations of whether a particular object is of a given type. That is, the class structures associated with the program are checked to determine the type of the particular object.
FIG. 1 is a diagrammatic representation of a conventional class structure. A class structure 102, i.e., a class hierarchy, includes a class 106 and sub-classes 110. In general, class 106 is an abstract class that may include any number of sub-classes 110. As shown, sub-class xe2x80x9c1xe2x80x9d 110a, sub-class xe2x80x9c2xe2x80x9d 110b, and sub-class xe2x80x9cNxe2x80x9d 110c are xe2x80x9cdirectxe2x80x9d sub-classes of class 106, while sub-class xe2x80x9cA1xe2x80x9d 110d is a direct sub-class of sub-class xe2x80x9c1xe2x80x9d 110a. Sub-class xe2x80x9cA1xe2x80x9d 110d may be considered to be an indirect sub-class of class 106 since sub-class xe2x80x9cA1xe2x80x9d 110d is a sub-class of sub-class xe2x80x9c1xe2x80x9d 110a, which is a sub-class of class 106.
Class 106 typically includes a variety of different functions, or methods. Each sub-class 110 generally contains a different set of functions. By way of example, sub-class xe2x80x9c1xe2x80x9d 110a will generally include functions that are specific to objects which are a part of sub-class xe2x80x9c1xe2x80x9d 110a. An object that is a member of class 106 may perform substantially all functions associated with class 106. Any object that is a member of any of sub-classes 110 is also a member of class 106. As such, an object that is a member of any of sub-classes 110 may also perform the functions associated with class 106. However, an object that is a member of a particular sub-class, e.g., sub-class xe2x80x9c1xe2x80x9d 110a, may not perform the specific functions associated with a different sub-class, e.g., sub-class xe2x80x9c2xe2x80x9d 110b. Therefore, a determination of which sub-class 110 an object belongs to effectively determines the functions that the object may perform.
A narrowing cast may be used at runtime to effectively view an object defined by class 106 as an object defined by sub-class xe2x80x9c1xe2x80x9d 110a. However, since the object defined by class 106 may be defined by sub-class xe2x80x9c2xe2x80x9d 110b, rather than by sub-class xe2x80x9c1xe2x80x9d 110a, a check is typically made to determine whether associated the object with sub-class xe2x80x9c1xe2x80x9d 110a is accurate. As will be appreciated by those skilled in the art, a check regarding whether an object is associated with sub-class xe2x80x9c1xe2x80x9d 110a is effectively a check to determine whether the object is associated with at least sub-class xe2x80x9c1xe2x80x9d 110a. In other words, an object that is associated with sub-class xe2x80x9cA1xe2x80x9d 110d will generally be determined to be associated with sub-class xe2x80x9c1xe2x80x9d 110a as well.
In a Java(trademark) environment, a function which determines the subtype of an object, e.g., an is_subtype function, may be statically encoded. While methods used to statically encode the function may vary, one method that is commonly used involves the use of a two-dimensional bit matrix where a bit at a location defined by (i,j) encodes the result of is_subtype(ti,tj). Using such a matrix, a subtype check effectively involves indexing into the matrix to determine the subtype of an object. However, the size of the matrix may be substantial, and the subtype checks are often slow due to the bit manipulation of instructions that is typically required.
In general, when sub-type checks are made, substantially all sub-types of a type, e.g., substantially all sub-classes of a class, must typically be checked to determine the sub-type of a particular object. In some hierarchical class structures, e.g., class structure 102 of FIG. 1, the number of sub-classes which must be checked may be relatively high. By way of example, some classes may have hundreds of associated sub-classes. As such, the implementation of subtype checks often proves to be inefficient when multiple subtypes are available, as is the case with interfaces defined in the Java(trademark) programming language. That is, when multiple subtypes are available, the checking of each subtype is typically time-consuming, as mentioned above. In addition, implementing subtype checks in a system which uses multiple inheritance layers, e.g., systems defined in the C++ programming language, is also often inefficient. For a system with multiple inheritance layers, subtype checks are generally difficult to implement efficiently due to the fact that each layer of inheritance must be checked.
The implementation of efficient subtype checks is important since the checks may occur frequently. When the checks occur frequently during the execution of a program the overhead associated with the checks may be relatively high. In some cases, a run-time subtype check, or test, may require on the order of approximately eight instructions which, as will be appreciated by those skilled in the art, may be significant with respect to the overall program, especially if repeated run-time subtype checks are made. Hence, the speed at which the program executes may be compromised by the frequent subtype checks.
Typically, when subtypes are checked during the execution of a program, substantially all classes and methods associated with the program must be known. Data structures are often constructed to list all classes and methods associated with a program, so that the classes and methods are readily accessible. In other words, data structures used in subtype checks must often be computed before program execution. Such data structures are often relatively large, and consume significant system resources. Further, the requirement that all classes and methods associated with a program are known is not compatible with systems which utilize dynamic linking, or dynamic class loading, as dynamic linking allows the classes and methods associated with the program to effectively change. The functionality of a program may be compromised by the inability to utilize dynamic linking. In an environment which uses dynamic linking, the data structures are generally recomputed after every operation which involves class loading, which is time-consuming and, hence, inefficient.
Therefore, what is desired is a method and an apparatus for improving the efficiency with which subtype checks may occur. More particularly, what is desired is a method and an apparatus for efficiently performing subtype checks without requiring that data structures be recomputed each time a class loading operation occurs.
Methods and apparatus for performing fast subtype checks during program execution are disclosed. According to one aspect of the present invention, a method for quickly and efficiently determining a type associated with an object that is a part of an object-based computing system includes obtaining a candidate type from a dynamic storage location that is associated with a class which is associated with the object, and comparing the candidate type against a first type that is potentially the same as the candidate type. A determination is then made as to whether the candidate type is substantially equal to the first type. When the determination is that the candidate type is substantially equal to the first type, an indication that the candidate type is substantially equal to the first type is provided.
In one embodiment, the candidate type obtained from the class associated with the object is obtained from a cache element in the class associated with the object. In such an embodiment, comparing the candidate type against the first type may include loading the candidate type from the cache element into a register, and comparing the contents of cache element to the first type.
According to another aspect of the present invention, a computer system is arranged to determine a type associated with a first object that is resident on the computer system. The computer system includes a processor, memory, and a loading mechanism arranged to load a candidate type into memory. The candid ate type is obtained from a class object that is associated with the first object. The computer system also includes a comparison mechanism arranged to compare the candidate type against a first type, and a determination mechanism arranged to determine whether the candidate type is substantially equal to the first type. An indicator in the computer system is arranged to provide an indication that the candidate type is substantially equal to the first type when it is determined that the candidate type is substantially equal to the first type.
In one embodiment, the computer system also includes a computing mechanism that is arranged to compute a type relationship between the class object and the first type when it is determined that the candidate type is not substantially equal to the first type. In such an embodiment, a determining mechanism may be used to determine whether a type relationship exists between the class object and the first type, and a storage mechanism may be arranged to store an indication of the first type into the cache element of the class object when it is determined that a type relationship exists between the class object and the first type.
According to still another aspect of the present invention, a method for performing a subtype check on an object that is a member of a particular class includes obtaining a stored element from a location associated with the particular class. The stored element includes information relating to a first subtype that is potentially associated with the object. The method also includes determining whether the information included in the stored element is related to an actual subtype that is associated with the object, and providing an indication that the information included in the stored element is related to the actual subtype when the stored element and the actual subtype are related. In one embodiment, the method also involves determining the actual subtype of the object when the information included in the stored element is not related to the actual subtype, as well as storing information relating to the actual subtype into the location associated with the particular class. The present invention will be better understood upon reading the following